import java.util.Arrays;

public class LongestIncreasingPath {

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(dfs(i, j, matrix, dp, -1), ans);
            }
        }
        return ans;
    }

    public int dfs(int i, int j, int[][] matrix, int[][] dp, int last) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] <= last) {
            return 0;
        }
        if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
        int[] temp = {1, -1};
        int res = 0;
        for (int k = 0; k < temp.length; k++) {
            res = Math.max(res, dfs(i + temp[k], j, matrix, dp, matrix[i][j]));
            res = Math.max(res, dfs(i, j + temp[k], matrix, dp, matrix[i][j]));
        }
        dp[i][j] = res + 1;
        return dp[i][j];
    }
}
